package Medium;

import Easy.LC0206;

import java.util.ArrayList;

public class LC2130 {

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }


    public int pairSum(ListNode head) {
        ListNode ptr = head;
        ArrayList<Integer> numbers = new ArrayList<>();
        while (ptr != null) {
            numbers.add(ptr.val);
            ptr = ptr.next;
        }

        int N = numbers.size();
        int pairSum = Integer.MIN_VALUE, maxPairSum = Integer.MIN_VALUE;
        for (int i = 0; i < N / 2; i++) {
            pairSum = numbers.get(i) + numbers.get(N - 1 - i);
            if (pairSum > maxPairSum) maxPairSum = pairSum;
        }

        return maxPairSum;
    }

    /**
     * 基于反转链表的解法（官方解法），相比自己的解法主要优势在于空间复杂度低。
     * 先用快慢指针找到链表的中间位置，然后反转后半部分的链表。
     */
    public int pairSumReverseList(ListNode head) {
        ListNode slow = head, fast = head.next;
        int N = 1;
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next.next; // 题目设置保证一定可以前进两步
            N++;
        }
        N *= 2;

        ListNode secondHead = slow.next;
        secondHead = reverseList(secondHead);
        ListNode left = head, right = secondHead;
        int pairSum, maxPairSum = Integer.MIN_VALUE;
        for (int i = 0; i < N / 2; i++) {
            pairSum = left.val + right.val;
            if (pairSum > maxPairSum) maxPairSum = pairSum;
            left = left.next;
            right = right.next;
        }

        return maxPairSum;
    }

    private ListNode reverseList(ListNode head) {
        if (head == null) return null;
        ListNode left = head, middle = head.next;
        if (middle == null) return head;
        ListNode right = middle.next;
        head.next = null;

        while (right != null) {
            middle.next = left;
            left = middle;
            middle = right;
            right = right.next;
        }

        middle.next = left;
        return middle;
    }

}
